package com.chilly.stack;

import java.util.*;

/**
 * 739. 每日温度
 * 请根据每日 气温 列表，重新生成一个列表。
 * 对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。
 * 如果气温在这之后都不会升高，请在该位置用 0 来代替。
 * <p>
 * Created by Chilly Cui on 2020/11/24.
 */
public class DailyTemperature {

    /*
    //第一种方法，从左到右遍历
    //原理是从左到右除了最后一个数其他所有的数都遍历一次，最后一个数据对应的结果肯定是 0，就不需要计算。
    //遍历的时候，每个数都去向后数，直到找到比它大的数，数的次数就是对应输出的值。
    public int[] dailyTemperatures(int[] T) {
        int length = T.length;
        int[] res = new int[length];
        for (int i = 0; i < length; i++) {
            int current = T[i];
            if (current < 100 && current > 30) {
                for (int j = i + 1; j < length; j++) {
                    if (T[j] > current) {
                        res[i] = j - i;
                        break;
                    }
                }
            }
        }
        return res;
    }*/

    /*// 第二种方法，怎样减少遍历次数呢？
    // 遍历一次数组中所有的值应该是少不了的，因为至少数组中每个值都需要计算一遍，所以时间复杂度肯定大于 O(n)。
    // 关键是要减少为每个数寻找值遍历次数。
    public int[] dailyTemperatures(int[] T) {
        int length = T.length;
        int[] result = new int[length];
        //从右向左遍历
        for (int i = length - 2; i >= 0; i--) {
            // j+= result[j]是利用已经有的结果进行跳跃
            for (int j = i + 1; j < length; j += result[j]) {
                if (T[j] > T[i]) {
                    result[i] = j - i;
                    break;
                } else if (result[j] == 0) { //遇到0表示后面不会有更大的值，那当然当前值就应该也为0
                    result[i] = 0;
                    break;
                }
            }
        }
        return result;
    }*/
    // 第二种方法，另一种写法
    public int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];
        //从后面开始查找
        for (int i = res.length - 1; i >= 0; i--) {
            int j = i + 1;
            while (j < res.length) {
                if (T[j] > T[i]) {
                    //如果找到就停止while循环
                    res[i] = j - i;
                    break;
                } else if (res[j] == 0) {
                    //如果没找到，并且res[j]==0。说明第j个元素后面没有
                    //比第j个元素大的值，因为这一步是第i个元素大于第j个元素的值，
                    //那么很明显这后面就更没有大于第i个元素的值。直接终止while循环。
                    break;
                } else {
                    //如果没找到，并且res[j]！=0说明第j个元素后面有比第j个元素大的值，
                    //然后我们让j往后挪res[j]个单位，找到那个值，再和第i个元素比较
                    j += res[j];
                }
            }
        }
        return res;
    }

    /*
    //第三种方法递减栈 ：
    // 存储下标的单调栈, 从栈底到栈顶的下标对应的温度列表中的温度依次递减
    public int[] dailyTemperatures(int[] T) {
        int length = T.length;
        int[] res = new int[length];
        Stack<Integer> stack = new Stack<>(); //存储数组元素的下标,而不是数组元素
        for (int i = 0; i < length; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                Integer pop = stack.pop();
                res[pop] = i - pop;
            }
            stack.add(i);
        }
        return res;
    }
    */

    public static void main(String[] args) {
        int[] temperatures = new int[]{73, 74, 75, 71, 69, 72, 76, 73};
        int[] res = new DailyTemperature().dailyTemperatures(temperatures);
        System.out.println(Arrays.toString(res));
        //预期输出为：[1, 1, 4, 2, 1, 1, 0, 0]
    }
}
